import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class DynamicSolution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int coin : coins) {
                int subProblem = i - coin;
                if (subProblem < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    public int[] advantageCount(int[] nums1, int[] nums2) {
       // 升序：o1 - o2，降序：o2 - o1
       // 创建一个大根堆，降序
        PriorityQueue<int[]> heap = new PriorityQueue<>(nums1.length, (o1, o2) -> o2[1] - o1[1]);
        for (int i = 0; i < nums1.length; i++) {
            heap.add(new int[]{i, nums2[i]});
        }
        Arrays.sort(nums1);
        int left = 0, right = nums1.length - 1;
        int[] res = new int[nums1.length];
        while (!heap.isEmpty()) {
            // poll()函数返回队首元素，并出列
            int[] top = heap.poll();
            if (nums1[right] > top[1]) {
                res[top[0]] = nums1[right--];
            } else {
                res[top[0]] = nums1[left++];
            }
        }
        return res;
    }
}
